package com.shawn.datastructure.tree;

/**
 * This entire class is used to build a Binary Tree data structure. There is the Node Class and the
 * Tree Class, both explained below.
 */


/**
 * A binary tree is a data structure in which an element
 * has two successors(children). The left child is usually
 * smaller than the parent, and the right child is usually
 * bigger.
 *
 * @author Unknown
 *
 */
public class BinaryTree {

	/**
	 * This class implements the nodes that will go on the Binary Tree.
	 * They consist of the data in them, the node to the left, the node
	 * to the right, and the parent from which they came from.
	 *
	 * @author Unknown
	 *
	 */
	class Node {

		/** Data for the node */
		public int data;
		/** The Node to the left of this one */
		public Node left;
		/** The Node to the right of this one */
		public Node right;
		/** The parent of this node */
		public Node parent;

		/**
		 * Constructor of Node
		 *
		 * @param value Value to put in the node
		 */
		public Node(int value) {
			data = value;
			left = null;
			right = null;
			parent = null;
		}
	}


	/** The root of the Binary Tree */
	private Node root;

	/**
	 * Constructor
	 */
	public BinaryTree() {
		root = null;
	}

	/**
	 * Method to find a Node with a certain value
	 *
	 * @param key Value being looked for
	 * @return The node if it finds it, otherwise returns the parent
	 */
	public Node find(int key) {
		Node current = root;
		while (current != null) {
			if (key < current.data) {
				if (current.left == null) {
					return current;    //The key isn't exist, returns the parent
				}
				current = current.left;
			} else if (key > current.data) {
				if (current.right == null) {
					return current;
				}
				current = current.right;
			} else {    // If you find the value return it
				return current;
			}
		}
		return null;
	}

	/**
	 * Inserts certain value into the Binary Tree
	 *
	 * @param value Value to be inserted
	 */
	public void put(int value) {
		Node newNode = new Node(value);
		if (root == null) {
			root = newNode;
		} else {
			//This will return the soon to be parent of the value you're inserting
			Node parent = find(value);

			//This if/else assigns the new node to be either the left or right child of the parent
			if (value < parent.data) {
				parent.left = newNode;
				parent.left.parent = parent;
				return;
			} else {
				parent.right = newNode;
				parent.right.parent = parent;
				return;
			}
		}
	}

	/**
	 * Deletes a given value from the Binary Tree
	 *
	 * @param value Value to be deleted
	 * @return If the value was deleted
	 */
	public boolean remove(int value) {
		//temp is the node to be deleted
		Node temp = find(value);

		//If the value doesn't exist
		if (temp.data != value) {
			return false;
		}

		//No children
		if (temp.right == null && temp.left == null) {
			if (temp == root) {
				root = null;
			}

			//This if/else assigns the new node to be either the left or right child of the parent
			else if (temp.parent.data < temp.data) {
				temp.parent.right = null;
			} else {
				temp.parent.left = null;
			}
			return true;
		}

		//Two children
		else if (temp.left != null && temp.right != null) {
			Node successor = findSuccessor(temp);

			//The left tree of temp is made the left tree of the successor
			successor.left = temp.left;
			successor.left.parent = successor;

			//If the successor has a right child, the child's grandparent is it's new parent
			if (successor.right != null && successor.parent != temp) {
				successor.right.parent = successor.parent;
				successor.parent.left = successor.right;
				successor.right = temp.right;
				successor.right.parent = successor;
			}
			if (temp == root) {
				successor.parent = null;
				root = successor;
				return true;
			}

			//If you're not deleting the root
			else {
				successor.parent = temp.parent;

				//This if/else assigns the new node to be either the left or right child of the parent
				if (temp.parent.data < temp.data) {
					temp.parent.right = successor;
				} else {
					temp.parent.left = successor;
				}
				return true;
			}
		}
		//One child
		else {
			//If it has a right child
			if (temp.right != null) {
				if (temp == root) {
					root = temp.right;
					return true;
				}

				temp.right.parent = temp.parent;

				//Assigns temp to left or right child
				if (temp.data < temp.parent.data) {
					temp.parent.left = temp.right;
				} else {
					temp.parent.right = temp.right;
				}
				return true;
			}
			//If it has a left child
			else {
				if (temp == root) {
					root = temp.left;
					return true;
				}

				temp.left.parent = temp.parent;

				//Assigns temp to left or right side
				if (temp.data < temp.parent.data) {
					temp.parent.left = temp.left;
				} else {
					temp.parent.right = temp.left;
				}
				return true;
			}
		}
	}

	/**
	 * This method finds the Successor to the Node given.
	 * Move right once and go left down the tree as far as you can
	 *
	 * @param n Node that you want to find the Successor of
	 * @return The Successor of the node
	 */
	public Node findSuccessor(Node n) {
		if (n.right == null) {
			return n;
		}
		Node current = n.right;
		Node parent = n.right;
		while (current != null) {
			parent = current;
			current = current.left;
		}
		return parent;
	}

	/**
	 * Returns the root of the Binary Tree
	 *
	 * @return the root of the Binary Tree
	 */
	public Node getRoot() {
		return root;
	}

	/**
	 * Prints leftChild - root - rightChild
	 *
	 * @param localRoot The local root of the binary tree
	 */
	public void inOrder(Node localRoot) {
		if (localRoot != null) {
			inOrder(localRoot.left);
			System.out.print(localRoot.data + " ");
			inOrder(localRoot.right);
		}
	}

	/**
	 * Prints root - leftChild - rightChild
	 *
	 * @param localRoot The local root of the binary tree
	 */
	public void preOrder(Node localRoot) {
		if (localRoot != null) {
			System.out.print(localRoot.data + " ");
			preOrder(localRoot.left);
			preOrder(localRoot.right);
		}
	}

	/**
	 * Prints rightChild - leftChild - root
	 *
	 * @param localRoot The local root of the binary tree
	 */
	public void postOrder(Node localRoot) {
		if (localRoot != null) {
			postOrder(localRoot.left);
			postOrder(localRoot.right);
			System.out.print(localRoot.data + " ");
		}
	}
}
